package com.heima.leetcode.practice;

/**
 * @author 勾新杰
 * @version 1.0
 * @description: leetcode 33 搜索旋转排序数组
 * @date 2024/12/11 10:10
 */
public class E33 {

    /**
     * <h3>方法一：线性查找优化，时间复杂度O(N)，但实际情况接近于O(logN)，因为很多情况都不会线性遍历完</h3>
     *
     * @param nums   旋转后的nums数组
     * @param target 目标值
     * @return 目标值在数组中的索引，没有找到返回-1
     */
    public int search1(int[] nums, int target) {
        int i;
        if (target < nums[0]) {
            i = nums.length - 1;
            while (i > 0 && nums[i] > nums[i - 1]) {
                if (nums[i] == target) return i;
                i--;
            }
        } else {
            i = 0;
            while (i < nums.length - 1 && nums[i] < nums[i + 1]) {
                if (nums[i] == target) return i;
                i++;
            }
        }
        if (nums[i] == target) return i;
        return -1;
    }

    /**
     * <h3>方法二：二分查找，时间复杂度O(logN)</h3>
     *
     * @param nums   旋转后的nums数组
     * @param target 目标值
     * @return 目标值在数组中的索引，没有找到返回-1
     */
    public int search2(int[] nums, int target) {
        int left = 0, right = nums.length - 1; // 搜索区间为 [left, right]
        // 1. 只要搜索区间内有元素，就继续进行循环
        while (left <= right) {
            // 1.1 计算中点索引，避免溢出，这里学习一种新的避免溢出方法
            int median = left + ((right - left) >> 1);
            // 1.2 先判断中点是不是目标值，如果是，提前结束循环，注意，这里已经判断中点值了
            if (nums[median] == target) return median;
            // 1.3 如果median左边是严格递增的
            if (nums[left] <= nums[median]) {
                // 1.3.1 如果中点左边是严格递增的，并且目标值在中点左边
                if (target < nums[median] && target >= nums[left]) {
                    right = median - 1;
                }
                // 1.3.2 如果中点左边是严格递增的，但是目标值在中点右边
                else {
                    left = median + 1;
                }
            }
            // 1.4 如果median右边是严格递增的
            else {
                // 1.4.1 如果中点右边是严格递增的，并且目标值在中点右边
                if (target > nums[median] && target <= nums[right]) {
                    left = median + 1;
                }
                // 1.4.2 如果中点右边是严格递增的，但是目标值在中点左边
                else {
                    right = median - 1;
                }
            }
        }
        return -1;
    }

    /**
     * <h3>方法三：二分查找，时间复杂度O(logN)，更好理解</h3>
     *
     * @param nums   旋转后的nums数组
     * @param target 目标值
     * @return 目标值在数组中的索引，没有找到返回-1
     */
    public int search3(int[] nums, int target) {
        int left = 0, right = nums.length - 1;
        while (left <= right) {
            int median = (left + right) >> 1;
            if (nums[median] == target) return median;
            // [left, median]是严格递增的
            if (nums[median] >= nums[left]) {
                if (nums[left] <= target && target < nums[median]) {
                    right = median - 1;
                } else {
                    left = median + 1;
                }
            }
            // nums[median]比nums[left]小，只能是一种情况：left在左边的递增区间，median在右边的递增区间
            else {
                if (nums[median] < target && target <= nums[right]) {
                    left = median + 1;
                } else {
                    right = median - 1;
                }
            }
        }
        return -1;
    }
}
